For many years, the performance of digital machine designs has been evaluated by performing static timing analysis on the designs. Timing analysis is a design automation tool which provides an alternative to the hardware debugging of timing problems. The program is intended to establish whether all the paths within the design meet stated predetermined timing criteria, i.e., whether data signals arrive at storage elements early enough for a valid capture, but not so early as to cause premature capture.
Propagation Segments, Timing Points, and Timing Graph:
Static timing analysis (STA) of digital systems has been used for decades to analyze the performance of digital designs. When performing an STA, elements of the design which can delay signals, such as logic gates, wires, and combinations thereof, are represented by propagation segments, also referred to as ‘psegs’, and which represent the delays of the elements. The prior art includes systems where delays are preferably determined by circuit simulations, as well as systems where delays are computed by various approximations to a simulated result. Each pseg includes two timing points, a “from” timing point representing an input to the delay element and a “to” timing point representing an output of the delay element. The timing graph of the design as a whole includes a full set of all the timing points and psegs of all logic gates, wires, and other delay elements in the design.
One conventional formulation of analysis partitions delays of the system into logic gate delays and interconnect delays, which are represented by propagation segments. An example thereof is shown in the relationship between an example of a combinational network, shown in FIG. 1 and a corresponding example of the formulation of a timing model shown in FIG. 2. For example, the delays of the NAND logic gate g4 in FIG. 1 are represented by three propagation segments shown in FIG. 2 from g4_i1 to g4_o, from g4_i2 to g4_o, and from g4_i3 to g4_o, referred to as an input to output to input or net/gate/net timing model.
Transistor Pins, Drivers, Receivers, Nets, Electrical Nodes
The representation generally views the output of a logic gate as a single point in the timing graph. Electrically, however, the logic gates consist of many transistors with many output electrical nodes. For example, referring to FIG. 3A, the inverter g1 and its input and output timing points g1_i and g1_o represent an approximate view of the electrical system shown in FIG. 3B. Herein, timing point g1_i can represent either of electrical nodes c or d, the gates of transistors p1 or n1, respectively. Similarly, timing point g1_o can represent either of electrical nodes e or g, the drains of transistors p1 or n1, respectively. A transistor pin can refer to a transistor gate, source, or drain. At the electrical circuit level of representation, each transistor pin is an electrical node in the circuit. Other electrical nodes in the circuit, such as a, b, f, or h, in FIG. 3B can be connected to other electrical elements, such as the resistors shown. A logical net is all the electrical nodes connected by resistors (or inductors), such as e, f, g, and h (FIG. 3B) and all the electrical elements interconnecting them. They represent one interconnect net at the electrical level. Alternatively, an interconnect net is the set of all the electrical nodes having DC connections and which will reach very similar voltages, if the circuit is operated slowly.
FIG. 4 illustrates in more detail gates g4, g5, g6, and g7 and the interconnect net between them. Shown is a resistive interconnect network linking electrical nodes a, b, c, d, e, f, g, h, i, j, k, l, and m, showing an example of an interconnect net to which the invention applies. Gate g4 is the driver of the interconnect net, and gates g5, g6, and g7 are receivers of the net. The output of gate g4 and the inputs of gates g5, g6, and g7 are logical ports of the net, i.e., places through which logic signals travel. Two of the logical ports include several electrical nodes. The driving logical port of the net, i.e., the output of gate g4 contains electrical nodes a, b, c, and d. One of the receiving logical ports of the net, the input to gate g7, includes electrical nodes l and m. It is possible for a logical port on a net to contain only a single electrical node. The input to gate g5 illustrates this possibility in the figure, and shows a receiving logical port consisting of only the single electrical node j.
Transistor pins which can pull the voltage of an interconnect net up or down (channel pins—either sources or drains) are considered driver pins, since they drive a logical signal into the net. Transistor gate pins sensing the voltage on an electrical node of an interconnect net are considered receiver pins, since they receive a logical signal from the net. At a coarser level of analysis, the logic gate inputs are also receivers on the nets to which they are connected, and logic gate outputs are also drivers on the nets to which they are connected. Additional drivers and receivers exist on nets at the boundary of the system under analysis. An input to the system under analysis (i.e., a primary input or PI) is a driver of the interconnect net that it is on. An output of the system under analysis (i.e., a primary output or PO) is a receiver of the interconnect net that it is on.
In an STA with an embedded simulator, the delay through a pseg is measured by applying a voltage waveform at an electrical node chosen as representing the “from” timing point of the pseg and measuring the voltage that the circuit simulation produced at an electrical node chosen to represent the “to” timing point of the pseg. More generally, the voltage applied to the “from” end may be applied to several electrical nodes.
Typically, one of the transistor pins is selected as “the” output timing point for a logic gate, resulting in numerical inaccuracies in the calculation of system delays through both the logic gate and the interconnect that it drives. A simplified example of the source of the inaccuracy is shown with reference to FIG. 5. Therein, an inverter consisting of pFET p1 and nFET n1 drives a net comprising electrical nodes b, c, and d and resistors r1 and r2. An example of the inaccuracy can occur if node b, the drain of pFET p1, is chosen to represent the output of the inverter. Considering the case of a rising input propagating through the inverter, the bulk of the electrical effect of the inverter on the output net is produced by nFET n1. The delay from the input of the inverter to its output is measured from electrical node a, through the intrinsic delay of nFET n1 (effectively to electrical node c, n1's drain), then backwards through r1 to node b. The delay through the net is then calculated forwards from node b through r1 (to node c) and through r2 to the receiver node d. The total delay through the two psegs, both logic gate and net, therefore counts the delay through r1 twice. Physically, however, the rising signal applied to the inverter input only needs to propagate through the nFET n1 to electrical node c, n1's drain, then through r2 to the receiver on electrical node d. This illustrates the primary prior art limitation.
A second prior art formulation of the static timing analysis is a “simulate-to-sinks” approach or input to input approach. An example thereof is shown in the relationship between an example of a combinational network, shown in FIG. 6A and a corresponding example of a “simulate-to-sinks” timing model shown in FIG. 6B. FIG. 6A illustrates logic gate g4, the interconnect net that gate g4 drives, and receiver logic gates g5, g6, and g7 on the net. FIG. 6B shows all the psegs derived from logic gate g4 and the following interconnect net. The psegs extend from all the inputs of gate g4, timing points g4_i1, g4_i2, and g4_i3 to all the receivers on the net it drives, timing points g5_i, g6_i, and g7_i. The second conventional approach avoids the inaccuracy due to resistances between the driving transistor pins of a logical net by including all of these pins within a single electrical simulation. The limitation of the methodology is that it increases the number of psegs needed. Generally, an M-input gate driving a net with N receivers needs M+N psegs to model it in the input-to-output-to-input approach, but M×N psegs in the input-to-input approach.
Biconnected Components and Articulation Vertices:
A biconnected graph (or component in an undirected graph) is a set of vertices and edges such that every pair of vertices in the set has at least two disjoint paths between them. An articulation vertex is a vertex in an undirected graph whose removal breaks up the graph into disconnected pieces. Biconnected components cannot be broken up into disconnected pieces by removal of a single vertex.
FIG. 7 illustrates what the partitioning of an undirected graph into biconnected components and articulation vertices does. The undirected graph with vertices a, b, c, d, e, f, g, h, i, j in FIG. 7A has only one vertex, c, which breaks the graph up into disconnected pieces if removed. The vertex is the sole articulation vertex for the graph. Splitting it up into two copies, c1 and c2, yields the two biconnected components, a, b, c1, d, e, and c2, f, g, h, i, j shown in FIG. 7B.